. A Proposed Level 3 Routing Algorithm for . Amateur Packet Radio . . By Lynn W. Taylor, WB6UUT . .Yea, from the table of my memory .I'll wipe away all trivial fond records. . -- Hamlet (Act I, Scene 5, line 98) . . According to the ISO Open Systems Interconnect model, the network controllers are responsible for the first three of the seven protocol layers in a packet switched network. Layer 1, the Physical level, is responsible for the physical aspects of communication (radios, modems, HDLC, baud rates). Layer 2, the Data Link level, is responsible for taking the physical medium and making it error-free, and dividing it up among the users. The third layer, called the Network, or Communications Subnet level determines the host-subnet interface and how packets are routed in the subnet. Levels 4 through 7 deal with issues that are beyond the scope of this paper. . . Routing is one of the key issues when defining a Communications Subnet Level protocol. The various routing algorithms can be divided into two categories, centralized (where some central station must know or discover the network topology, and serve as a clearinghouse for routing) and decentralized (where each TNC can handle at least part of the routing task). Centralized algorithms must be designed to recover when the master station crashes, and each station must know how to reach the router itself. Decentralized algorithms require each station to know how to pass traffic to other stations in the net; to accomplish this, the TNC needs to find out something about the nework topology. . . I am going to discuss two specific routing algorithms, the advantages and drawbacks of each, and why I believe we should select a decentralized algorithm for Amateur use. None of this material is original, and most is discussed at some length in the computer science literature. Some of the combinations of this information are new, particularly as they relate to the specific problems of Amateur usage. . . The first algorithm has a couple of advantages, and one major disadvantage. This algorithm does not require any special knowlege of the network topology, other than a list of stations that the TNC can hear. When the TNC receives a packet addressed to someone other than itself, it simply passes it on to everyone it can hear except the station it received it from. The algorithm is appropriately called Flooding. . . Flooding is easy to understand, and easy to implement. The problem comes when the load on the network increases. Since each packet will pass through every single node in the network, and many of them more than once, the amount of traffic generated by simply saying "Hi" can be staggering. Also, steps must be taken to prevent packets from looping forever through the network. The simplest case of this is a 4 station net (A, B, C and D) where all 4 stations can hear each other. If A originates a packet for D, it passes it to all 3 stations it can hear. B passes it to both C and D, where D accepts it, and C passes it to A and D. D has already got the packet and ignores the duplicate, while A passes it to B and D. Again, D discards it, and B passes it around. At the same time, packets are flowing in the opposite direction around the same loop. While this simple case could be easily fixed, it becomes more complex in a larger net. One solution is to limit the life of any given packet to a certain number of hops, but this still generates a lot of unnecessary traffic. . . A better algorithm would require each TNC to have a table giving the address of each node in the network, some measure of the distance to that station, and the address of the next station along a path to that station. A hypothetical 5 station net, and each node's tables is shown below: . . A <---> B <---> C <---> D <---> E . . B 1 B A 1 A A 2 B A 3 C A 4 D . C 2 B C 1 C B 1 B B 2 C B 3 D . D 3 B D 2 C D 1 D C 1 C C 2 D . E 4 B E 3 C E 2 D E 1 E D 1 D . . In this example, the available communications paths are shown by arrows (i.e. A cannot communicate directly with C). Note that each station knows how far away all the other stations are, and who is the next station in the chain. If A wants to talk to D, A knows to pass traffic to D, and it will take 3 hops to get there. It is up to B to know who to pass these packets on to. . . The problem with this method is easy to see -- where do these tables come from? In the proposed WestNet protocol, which defines a long-haul network for linking geographically seperated LANs, a similar algorithm is used which assumes all nodes internal to the network will stay on. In other words, this network is static (because all the nodes are dedicated devices to be installed on mountaintops). In a local network, stations (nodes) tend to appear and disappear frequently. . . In a dynamic network, the answer to the question must be "from the network itself." This further divides into two problems: how does a new station get it's initial table, and how do we make sure the table each node has is up to date. To clarify this problem, lets add station F to our earlier network: . . A <---> B <---> C <---> D <---> E . ^ ^ . | | . -------------> F <------------- . . In this example, A should now pass traffic for E through F, while traffic for D can follow it's previous route, or as efficiently through E and F. If all stations listen for new stations on the air, and F comes on and sends an "I'm here" (or CQ) packet, A and E can detect F's presence, connect with F to make sure they can communicate, and pass copies of their routing tables. By taking the best information from both tables, F can build it's initial table: . . A 1 A . B 2 A . C 3 E . D 2 E . E 1 E . . There are two equally good paths from F to C (through E and D, and through A and B), F selects these at random. . . Also, the rest of the net need to be told about the new network topology. First, A (and simultaneously, E) tells everyone it can hear that F is one hop away from it. B checks it's routing tables, decides that this is good news, and passes the news along to everyone it can hear, etc. This is the flooding algorithm again, with a twist; stations only pass on good news, so if a station already has a path of length N, it only passes on news of a path of N-1. In other words, when B announces to A and C that "I'm 2 hops from F", C is glad to hear, while A could care less, since A is only 1 from F, while C didn't even know F existed. C will wind picking the first path to F it hears about, since it has 2 paths of length 3 to F. This also means that C might use a different path to F than F would use to C; this does not matter since each have the same length. . . F would also pass on the news of it's complete routing table, since the whole table is news to it. This way, A learns of the new path through F to E and E learns about it's new paths. The new tables would look like this: . . B 1 B A 1 A A 2 B A 3 A A 2 F . C 2 B C 1 C B 1 B B 2 C B 3 D . D 3 B D 2 C D 1 D C 1 C C 2 D . E 2 F E 3 C E 2 D E 1 E D 1 D . F 1 F F 2 A F 3 A F 2 E F 1 F . . A <---> B <---> C <---> D <---> E . ^ ^ . | | . -------------> F <------------- . . A 1 A . B 2 A . C 3 E . D 2 E . E 1 E . . Adding a node to the network is easy compared to what happens when a node leaves the net. Having a node tell the net it's leaving is impractical, because that node may not be able to tell the net because of hardware failures, power failures, or propogation changes. One solution would be for a node to report to the rest of the net that node X is unreachable whenever it can't pass traffic on to X. This bad news would be passed through the net until it reaches X, which would then tell those stations it can still reach that it is indeed still reachable, generating a new set of entries in the network tables. . . As an example, A is passing traffic for E through F when F goes off the air. A, realizing that it can't pass traffic through F announces to B that E is unreachable. B passes this news to C, who passes on to D, and eventually to E. At this point, E has been erased from everyone's routing tables. E would then tell D "I'm still accessable", D reports to C that "E is still 1 hop from me", and the good news passes through the net (and contradicts any bad news still circulating). A may now use the longer path through B, C and D, and the network has recovered from the loss of the path to E through F. . . The problem of updating the routing tables is the most serious drawback of this algorithm, and I am not suggesting that the method I have explained above is the best. In Computer Networks by Andrew Tannenbaum, he points out that "good news travels fast" while bad news may take awhile to propogate through the network, especially where looped paths exist. By completely eliminating a station from the network tables and re-inserting it, many of these kinds of problems may be avoided. . . I have explained two decentralized routing algorithms. These algorithms allow the nodes themselves, on an equal basis, to decide how to route data in the net, and dynamically alter the routing when the network composition changes. What are the problems involved in a centralized algorithm? . . Centralized algorithms require a single station to have complete knowlege of the network. To do this, the master station must probe the network, and pass on it's discoveries to the rest of the net. The master must either be a unique station type, or, in a homogeneous network, a station must be selected to be the master. A new station, when it comes on the air, must be able to tell the master it is on, and, if it can't reach a master, would most likely become one. Problems exist, in the case of two networks "growing" together (more than one master), and when the master fails. Depending on the implementation, a network may continue to operate without the master based on old information the master distributed, or collapse when the master disappears. Either solution would be undesirable. . . I have shown that a properly designed decentralized system will not suffer unduly from the loss of any single critical station, and recover from the loss of any node in a reasonable manner. Centralized systems rely on the master station discovering the complete network topology, finding changes due to propogation, etc. and distributing this info. Since Amateur packet nets are very dynamic, it is probable that the master will be lost, causing the net to crash, or continue on without any direction. . . While I feel the decentralized approach is best, the possibility of reasonable mechanisms for operating centralized networks, hybrid networks, rings, token passing schemes, and other are all worth investigating. My main purpose is to serve as a catalyst for further discussion. . . What's in a Layer? . or . Why Layer Three is not Linking . . by Lynn W. Taylor, WB6UUT . . I have been reading a lot of papers recently discussing some planned hardware, and some "wish lists" for layer 3 (and higher) protocols. In most of these, it seems to me that the authors have drifted from the goal of defining what should be done at the Communications Subnet level (layer 3) of the ISO model. To explain this level as I understand it, I am going to present an analogy, discuss the issues I feel are and aren't important, and suggest why layer 3 and linking should be considered together. Finally, I will present my layer 3 "wish list." . . As a brief review, layer 1 (physical) gives us a communications media or channel. Our specific choices on this later are Radio, HDLC, Bell 202 and 1200 baud; it does not deal with error rates or channel sharing. . . On layer 2, we take our channel resource and split it up (in time) into 'virtual' channels, and we take steps to insure a (nearly) error free channel. Our specific layer 2 is AX.25, which defines a Local Area Net, and provides a means to extend the LAN where signal propogation is inadequate to allow the most distant users to communicate (digipeating). In the Los Angeles/San Diego LAN, the most distant users are over 120 miles apart; the user must have some knowlege of the network topology (who can hear whom) in order to communicate with other users. . . Another network worth considering is the telephone system. In this network, we have a physical level (baseband audio on wires), a data link layer (the local office switch), and a good example of a communications subnet layer. Layer 1 is handled by wire. On layer 2, 10,000 users (which share a prefix) can be directly connected together by switches in a single exchange. On layer 3, things get more complex. . . While only a short distance apart, it is not possible for my phone (497 prefix) to be connected to my parents (494 prefix); we are in seperate "local networks" or local exchanges. In this trivial case (both exchanges are in the same building), my exchange selects a 'trunk' which connects it to the other exchange, and then on to the call's destination. . . In the case of a longer call (from my home in Southern California to Pete Eaton in Saint Louis, for example), I "invoke" a long range network (which my exchange knows how to access), and trunks are selected connecting to various switching centers, into Pete's exchange, and on to Pete's phone. . . The important thing to note here is that, as far as I can tell, my phone can directly be connected to any phone in my local dialing area (a geographically large LAN), or any other phone in the world -- without my knowing (or even being able to find out) which trunks, exchanges, routing centers, etc. are involved. In other words, the task of the communications subnet layer is to make it appear that every station in the net can be directly connected to every other. . . As a user in the LAN, what I should be able to do is exactly the same as when I dial my telephone -- connect to any other station by simply specifying the call sign of that station. The connect may fail because the destination node is down, busy, or simply unreachable. In a seperate paper, I have suggested a decentralized mechanism which would allow dynamic routing of packets as the network changes -- other algorithms are possible, including centralized and hybrid networks. What ever method is finally chosen, it should appear to the user that every station in the net can talk directly to every other node in the net. . . Notice that many of these statements are as valid for a long-distance network (AMICON) as for a local network, and pehaaps even mre valid. It should not be necessary for me to specify that my data be transferred via Los Angeles, Las Vegas, Salt Lake City, etc. to get to Saint Louis; especially if the route via San Diego, Tucson, Taos, Houston, etc. is less congested, or if a critical node is down along the other route. . . I am concerned when other issues start "invading" the communications subnet, such as non-connect communications, such as sattelite (PACSAT) routing, and mail-type services. In the case of message traffic, Bulletin boards and PACSAT gateways can provide the necessary store-and-forward services. In order to incorporate this in a protocol, w must deal with such issues as how to store this data (provide some nodes with lots of memory?), how to access this distributed database, and how long to keep these messages around. In my opinion, this is an application of the network best dealt with at the application level (layer 7). . . In the phone system, special procedures are necessary to access the long-range network (dialing '1'). I don't think it is unreasonable to set up a gateway to a long-haul network, and require the user to connect to this station to access distant networks. A question here is, do I want my TNC to indicate that I am connected to the distant station, or is it OK or me to be connected to the gateway itself. A good option here might be to connect to the linker, give it the call I want to talk to, and disconnect, allowing it to connect (at layer 3) to me when the path is established. . . In other words, we want a communications subnet to be usable without any specialized knowlege of it's topography. In order to reach this goal, layer 3 is concerned with routing; it does not state whether we are extending our LAN, or linking distant networks. . . While these are seperate issues, I don't think one can be considered without the other. On one hand, linking LAN's is much more difficult if you must give detailed routing information; some kind of layer 3 is almost essential for the long-haul net On the other hand, the LAN layer 3 would require each node to have some information about the network it's in; if a long-haul gateway knows who it can reach in it's LAN, it can be queried for a specific station -- this query could provide a "directory assistance" function. Using "area codes" suggests that a "packet directory" would need to be published. A scheme allowing a query throughout the long-haul network would handle this case, and also allow me to travel to another area and receive connects through the appropriate gateway. . . Now that I have presented some of my thoughts on the topics of linking and layer 3, I would like to present my "wish list." I would like to see a communications subnet layer running on the TNC in the LAN, allowing me to connect to any station in the net by requesting a connect to that station. I want the algorithm to be able to handle changing topography (due to stations going on/off line, or changing propogation and dynamically re-route my packets; this does not allow for a user-specified routing, since the network has the authority to change the routing. I want a similar capability to exist in the long-haul network, plus a 'directory assistnce' capability allowing me to access a station by call sign without knowing exactly where he is in the net. . . I think this is attainable using present hardware. As I discussed in my previous paper ("A Proposed Layer 3 Routing Algorithm"), I feel it is possible to have dynamic routing in a connection environment. The tables necessary to handle this in the LAN make the necessary data available to the long-haul net. This will allow a smoothly operating local net, and an easily accessable long-haul network which is fairly tolerant of failures; it should also be simple enough to implement. [End of Article]